import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-08-16
 * Time: 23:01
 */

public class Solution {

    /**
     *  排序
     */
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int len = citations.length;
        for (int i = 0; i < len; i++) {
            if (citations[i] >= (len-i)) {
                return len-i;
            }
        }
        return 0;
    }


    /**
     *  计数排序
     */

    public int hIndex2(int[] citations) {
        int n = citations.length, tot = 0;
        int[] counter = new int[n + 1];
        // 下标 index 表示引用数量为 index 的文章的数量
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n) {
                counter[n]++;
            } else {
                counter[citations[i]]++;
            }
        }
        // 计算引用数量 > 文章数量的 那个最大数字
        for (int i = n; i >= 0; i--) {
            tot += counter[i];
            if (tot >= i) {
                return i;
            }
        }
        return 0;
    }


    /**
     *  二分查找
     *  以 [0, n] 开始二分, 查找符合条件的 h
     */
    public int hIndex3(int[] citations) {
        int left=0,right=citations.length;
        int mid=0,cnt=0;
        // 二分查找符合条件的 h
        while(left<right){
            // +1 防止死循环
            mid=(left+right+1)>>1;
            cnt=0;
            for(int i=0;i<citations.length;i++){
                if(citations[i]>=mid){
                    cnt++;
                }
            }
            if(cnt>=mid){
                // 要找的答案在 [mid,right] 区间内
                left=mid;
            }else{
                // 要找的答案在 [0,mid) 区间内
                right=mid-1;
            }
        }
        return left;
    }
}
